A. Field of the Invention
The present invention relates generally to information retrieval and, more particularly, to assigning ranking values to a set of linked nodes.
B. Description of Related Art
The World Wide Web (“web”) contains a vast amount of information. Search engines assist users in locating desired portions of this information by cataloging web pages. Typically, in response to a user's request, the search engine returns references to documents relevant to the request.
Search engines may base their determination of the user's interest on search terms (called a search query) entered by the user. The goal of the search engine is to identify links to high quality relevant results based on the search query. Typically, the search engine accomplishes this by matching the terms in the search query to a corpus of pre-stored web documents. Web documents that contain the user's search terms are considered “hits” and are returned to the user.
The hits returned by the search engine are typically sorted based on relevance to the user's search terms. Determining the correct relevance, or importance, of a web page to a user, however, can be a difficult task. For one thing, the relevance of a web page to the user is inherently subjective and depends on the user's interests, knowledge, and attitudes. There is, however, much that can be determined objectively about the relative importance or quality of a web page. Existing methods of determining relevance are based on matching a user's search terms to terms indexed from web pages. More advanced techniques determine the importance of a web page based on more than the content of the web page. For example, one prior method, called PageRank™, assigns a degree of importance to a web page based on the link structure of the web. An implementation of PageRank™ is described in U.S. Pat. No. 6,285,999, the contents of which are incorporated by reference herein.
Web pages that are ranked highly by a ranking technique such as PageRank™ tend to be presented more prominently to the end-user than lower ranked web pages. Accordingly, higher ranking web pages tend to have higher selection (“click-through”) rates than web pages with lower rankings Since many web sites would like to increase traffic, higher rankings are desirable.
Some entities, such as certain on-line commercial interests, may attempt to artificially improve their ranking in order to get higher user traffic. In the case of the PageRank™ ranking system, for example, which is based on links between pages, the owners or creators of some web sites may, based on their knowledge of the PageRank™ algorithm, attempt to optimize their link structure to improve their PageRank™ rating. Another method of artificially boosting a PageRank™ ranking is based on paying another site, with high rank, to link to the web site. In general, any artificial attempts to improve the ranking of a web site by “tuning” the web site to a specific ranking algorithm does not improve the user-perceived quality of the web site and may thus decrease the overall performance of the search engine.
Thus, there is a need in the art for ranking techniques that deemphasize artificial attempts to boost the ranking of a web site.